package sort;

import java.util.Arrays;

/**
 * 堆排序，构造大根堆，再依次将堆顶元素放到数组末尾
 */
public class HeapSort {

    public static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 依次取出堆顶元素放到数组末尾
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }

    /**
     * 调整根堆，如果左右孩子中有大于当前根节点的，找两者中最大的与根节点交换
     *
     * @param arr
     * @param n   当前数组长度
     * @param i   当前可能需要调整的位置
     */
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 3, 8, 2, 9, 1};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}
